#include <iostream>
#include <assert.h>
#include <stdio.h>
using namespace std;

typedef  char DateType;

struct ListNode
{
    DateType _date;
    ListNode *_next;
    ListNode(const DateType a):_date(a),_next(NULL)
    {}
};
ListNode *LinkListPushBack(ListNode **head,DateType value)
{
    assert(head);
    ListNode *new_node=new ListNode(value);
    new_node->_next=NULL;
    if(NULL==(*head))
    {
        *head=new_node;
    }
    else
    {
        ListNode *cur=(*head);
        while(cur->_next!=NULL)
        {
            cur=cur->_next;
        }
        cur->_next=new_node;
    }
    return new_node;
}
ListNode *LinkListPushFront(ListNode **head,DateType value)
{
    assert(head);
    ListNode *new_node=new ListNode(value);
    if(NULL==*head)
    {
        *head=new_node;
    }
    else
    {
        new_node->_next=(*head);
        (*head)=new_node;
    }
    return new_node;
}
void LinkListPrint(ListNode *head,const char *msg)
{
    if(NULL==head)
    {//空链表
        return;
    }
    puts(msg);
    ListNode *cur=head;
    while(cur!=NULL)
    {
        printf("[%c] ",cur->_date);
        cur=cur->_next;
    }
    cout<<"\n";
}
//方法一：用递归的方式来逆序输出
void LinkListReversePrint(ListNode *head)
{
    if(NULL==head)
    {
        return;
    }
    if(head->_next!=NULL)
    {
       LinkListReversePrint(head->_next); 
    }
    printf("[%c] ",head->_date);
}
//方法二：用循环的方式来逆序输出
typedef ListNode * SeqDataType;
const int maxsize=100;//此处需要自己维护栈的大小
struct SeqStack
{
    SeqDataType _data[maxsize];
    size_t _size;
    SeqStack():_size(0)
    {}
};
void SeqStackPush(SeqStack *seq,SeqDataType value)
{
    assert(seq->_size<maxsize);
    seq->_data[seq->_size]=value;
    seq->_size++;
}
void SeqStackPop(SeqStack *seq)
{
    if(seq->_size==0)
    {
        return;
    }
    seq->_size--;
}
int SeqStackTop(SeqStack *seq,SeqDataType *tmp)
{
    if(seq->_size==0)
    {
        return 0;
    }
    *tmp=seq->_data[seq->_size-1];
    return 1;
}
void PrintStack(SeqStack *seq)
{
    size_t i=0;
    for(i=0;i<seq->_size;++i)
    {
        printf("[%c] ",seq->_data[i]->_date);
    }
}
void LinkListReversePrint_Cycle(ListNode *head)
{
    if(NULL==head)
    {//链表为空
        return;
    }
    SeqStack seq;
    ListNode *cur=head;
    while(cur!=NULL)
    {
        SeqStackPush(&seq,cur);
        cur=cur->_next;
    }
    ListNode *tmp=head;
    while(SeqStackTop(&seq,&tmp)!=0)
    {
        printf("[%c] ",tmp->_date);
        SeqStackPop(&seq);
    }
    printf("\n");
}
void TestList()
{
    ListNode *head=NULL;
    LinkListPushFront(&head,'d');
    LinkListPushFront(&head,'c');
    LinkListPushFront(&head,'b');
    LinkListPushFront(&head,'a');
    LinkListPrint(head,"头插4个元素");
    //LinkListReversePrint(head);
    LinkListReversePrint_Cycle(head);
}
int main()
{   
    TestList();
    return 0;
}
